//
// Created by 朱语 on 2022/8/4.
//

#ifndef DS_GRAPH_H
#define DS_GRAPH_H

#include <vector>
using namespace std;


class graph {
private:
    vector<vector<int>> _graph;//邻接矩阵
    int size;
    int init_weight;
    void dfs(vector<bool> & visited, int vertex);
    void dfs_iter(vector<bool> & visited, int start);
    void bfs_iter(vector<bool> & visited, int start);

    void path_print(vector<int> & dist , vector<int> & parent,int start, int end);

public:
    graph();
    explicit graph(int side, int init_side = 0);
    ~graph();

    //设定图的边，可以为有权图
    void build(vector<vector<int>>& pair);

    //两种遍历方法
    void DFS(int start = 0);//depth first search
    void BFS(int start = 0);//broad first search

    //检查是否联通
    bool connected();

    //最短路径
    void UnWeighted(int start = 0);//无权图，单源
    void Dijkstra(int start = 0);//有权图，单源
    void Floyd();//有权图，多源

    //最小生成树 minimum spanning tree
    //start只影响最后查看使树的根，不影响树形状本身
    void Prim(int start = 0);//基于BFS，小树长大
    void Kruskal();//树聚合成森林


};


#endif //DS_GRAPH_H
